package map.hashBucket;

import java.util.Random;

// key-value 模型
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;


        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //扩容的素数数组
    private static int[] primes = {
                11, 23, 53, 97, 193, 389, 769,
                1543, 3079, 6151, 12289,
                24593, 49157, 98317, 196613,
                393241, 786433, 1572869, 3145739,
                6291469, 12582917, 25165843, 50331653,
                100663319, 201326611, 402653189, 805306457,
                1610612741
    };

    private Node[]  array;

    private int primeSize = 0;
    private int size = 0;   // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    private static final int DEFAULT_SIZE = 11;//默认桶的大小

    public int put(int key, int value) {
        //计算下标的位置
        int index = hashCode(key);
        Node cur = array[index];
        //遍历链表中是否存在key，存在更改value值
        while(cur != null){
            if(cur.key == key){
                cur.value = value;
                return -1;
            }
            cur = cur.next;
        }
        //hashBucket中没有key,进行头插
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;

        size++;
        //扩容
        if(loadFactor() >= LOAD_FACTOR){
            resize();
        }

        return index;
    }

    public int getSize() {
        return size;
    }

    //获取哈希值
    public int hashCode(int key){
        return key % array.length;
    }

    //扩容
    private void resize() {
        //创建更大的新数组
        Node[] newArray = new Node[primes[primeSize++]];
        //将老数组的元素转移到新的数组中
        for(int i = 0; i < array.length; i++){
            Node cur = array[i];
            while(cur != null){
                Node newNode = new Node(cur.key, cur.value);
                int index = cur.key % newArray.length;
                //头插
                newNode.next = newArray[index];
                newArray[index] = newNode;
                cur = cur.next;
            }
        }
        //新数组替换旧数组
        array = newArray;
    }

    //求负载因子
    private double loadFactor() {
        return size * 1.0 / array.length;
    }

    //构造函数
    public HashBucket() {
        this.array = new Node[primes[primeSize++]];
    }

    //获取关键字为key的value，存在返回value，不存在返回null
    public Integer get(int key) {
        int index = hashCode(key);
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除关键字为key的元素
    public boolean remove(int key){
        int index = hashCode(key);
        Node cur = array[index];
        //空链表，删除失败，返回false
        if(cur == null){
            return false;
        }
        //头结点等于key
        if(cur.key == key){
            array[index] = cur.next;
            size--;
            return true;
        }
        //遍历链表找到要删除的结点，并删除
        Node prev = cur;
        cur = cur.next;
        while(cur != null){
            if(cur.key == key){
                prev.next = cur.next;
                size--;
                return true;
            }
            prev = cur;
            cur = cur.next;
        }
        //删除失败，返回false
        return false;
    }

    public static void main(String[] args) {
        HashBucket hash = new HashBucket();
        Random random = new Random();
        for(int i = 1; i <= 20; i++){
            int num = random.nextInt(100) + 1;
            hash.put(i, num);
        }
        System.out.println(hash.get(10));
        System.out.println(hash.getSize());
        System.out.println(hash.remove(11));
        System.out.println(hash.remove(111));
    }
}
